第1章 イントロダクション

p.1~p.23

ざっくり

イントロダクションなので、2章以降に出てくる用語とか概念とかを先に説明しちゃうよ！というやつ。

数学(指数対数、O記法、確率、ランダム化等)

実行時間、メモリ使用量

「インターフェース」は対応してる操作とその操作の意味を定義するもの

データ構造にとってのジョブ(RPGに出てくるやつ)みたいな。「回復術士のジョブは治癒と強化魔法が使えるよ～」みたいなノリで「USetインターフェースはsize(), add(x), remove(x), find(x)に対応している」って言う。

「セマンティクス」…おきもち、効果みたいな(雑)

数学

基本コンピュータ界隈の何も書いてないlogは底がeじゃなくて2

lnはlog_eの略したやつ

nCkは（）の上にn、下にk…みたいな行列的な表し方をしている

漸近記法

ランダム性と確率

インジケータ確率変数…の「期待値の定義の方を使うと難しい」の式変形、2行目から3行目何をしている…？

計算モデル

ワード幅wについて、データ構造に格納されうる要素数がnであればw > log n ということを仮定する

「ワード幅」はメモリの1セルあたりが何ビットですか、みたいな"字幅"的なもの

ワード幅4だとメモリ内は 0010 1101 0011 0010 0101 1101 1010 みたくなってる

メモリブロックへのポインタは1ワードに収まってほしい（その方がモデルを考えやすいので）

要素数n通りを全て参照とかで指し示すためにはlog nビット必要(たとえば2進数で8個の要素を表したいとき、少なくとも3桁が必要 000 ~ 111 みたいな)

よってw > log n